# 啊哈！算法 第4章 第2节
# 创建地图
map = [[0 for i in range(5)] for j in range(6)]
for i in range(5):
    map[0][i] = 1
for j in range(6):
    map[j][0] = 1
map[1][3] = 1
map[3][3] = 1
map[4][2] = 1
map[5][4] = 1
# print(map)

# 位移数组 右 下 左 上
walk = [[1, 0], [0, 1], [-1, 0], [0, -1]]

# 搜索地图，需要记录下当前位置和步数
aim = [4, 3]
min_step = float('inf')
step = 0
# 记录路径，也可以直接打印结果地图（地图数组中包含了走过的路径）
line = []


def find(x, y, step):
    if x == aim[1] and y == aim[0]:
        global min_step
        if step <= min_step:
            min_step = step
            # line.append([y,x])
            # print(line)
            print(min_step)
            print(map)
            # line.remove([y,x])
        return
    for k in range(4):
        new_x = x + walk[k][0]
        new_y = y + walk[k][1]
        if new_x < 5 and new_y < 6:
            if map[new_y][new_x] != 1 and map[new_y][new_x] != 2:
                map[new_y][new_x] = 2
                step += 1
                # print(x,y)
                line.append([new_y, new_x])
                find(new_x, new_y, step)
                line.remove([new_y, new_x])
                map[new_y][new_x] = 0
                step -= 1
    return


find(1, 1, 0)
